home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / util / BitSet.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  16.2 KB  |  497 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)BitSet.java    1.34 98/05/06
  3.  *
  4.  * Copyright 1995-1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. import java.io.*;
  18.  
  19. /**
  20.  * This class implements a vector of bits that grows as needed. Each 
  21.  * component of the bit set has a <code>boolean</code> value. The 
  22.  * bits of a <code>BitSet</code> are indexed by nonnegative integers. 
  23.  * Individual indexed bits can be examined, set, or cleared. One 
  24.  * <code>BitSet</code> may be used to modify the contents of another 
  25.  * <code>BitSet</code> through logical AND, logical inclusive OR, and 
  26.  * logical exclusive OR operations.
  27.  * <p>
  28.  * By default, all bits in the set initially have the value 
  29.  * <code>false</code>. 
  30.  * <p>
  31.  * Every bit set has a current size, which is the number of bits 
  32.  * of space currently in use by the bit set. Note that the size is
  33.  * related to the implementation of a bit set, so it may change with
  34.  * implementation. The length of a bit set relates to logical length
  35.  * of a bit set and is defined independently of implementation.
  36.  *
  37.  * @author  Arthur van Hoff
  38.  * @author  Michael McCloskey
  39.  * @version 1.34, 05/06/98
  40.  * @since   JDK1.0
  41.  */
  42. public class BitSet implements Cloneable, java.io.Serializable {
  43.     /*
  44.      * BitSets are packed into arrays of "units."  Currently a unit is a long,
  45.      * which consists of 64 bits, requiring 6 address bits.  The choice of unit
  46.      * is determined purely by performance concerns.
  47.      */
  48.     private final static int ADDRESS_BITS_PER_UNIT = 6;
  49.     private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
  50.     private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;
  51.  
  52.     /**
  53.      * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
  54.      * bit position i % 64 (where bit position 0 refers to the least
  55.      * significant bit and 63 refers to the most significant bit).
  56.      *
  57.      * @serial
  58.      */
  59.     private long bits[];  // this should be called unit[]
  60.  
  61.     private transient int unitsInUse; //# of units in logical size
  62.  
  63.     /* use serialVersionUID from JDK 1.0.2 for interoperability */
  64.     private static final long serialVersionUID = 7997698588986878753L;
  65.  
  66.     /**
  67.      * Given a bit index return unit index containing it.
  68.      */
  69.     private static int unitIndex(int bitIndex) {
  70.         return bitIndex >> ADDRESS_BITS_PER_UNIT;
  71.     }
  72.  
  73.     /**
  74.      * Given a bit index, return a unit that masks that bit in its unit.
  75.      */
  76.     private static long bit(int bitIndex) {
  77.         return 1L << (bitIndex & BIT_INDEX_MASK);
  78.     }
  79.  
  80.     /**
  81.      * Set the field unitsInUse with the logical size in units of the bit
  82.      * set.  WARNING:This function assumes that the number of units actually
  83.      * in use is less than or equal to the current value of unitsInUse!
  84.      */
  85.     private void recalculateUnitsInUse() {
  86.         /* Traverse the bitset until a used unit is found */
  87.         int i;
  88.         for (i = unitsInUse-1; i >= 0; i--)
  89.         if(bits[i] != 0)
  90.         break; //this unit is in use!
  91.  
  92.         unitsInUse = i+1; //the new logical size
  93.     }
  94.  
  95.     /**
  96.      * Creates a new bit set. All bits are initially <code>false</code>.
  97.      */
  98.     public BitSet() {
  99.     this(BITS_PER_UNIT);
  100.     }
  101.  
  102.     /**
  103.      * Creates a bit set whose initial size is large enough to explicitly
  104.      * represent bits with indices in the range <code>0</code> through
  105.      * <code>nbits-1</code>. All bits are initially <code>false</code>. 
  106.      *
  107.      * @param     nbits   the initial size of the bit set.
  108.      * @exception NegativeArraySizeException if the specified initial size
  109.      *               is negative.
  110.      */
  111.     public BitSet(int nbits) {
  112.     /* nbits can't be negative; size 0 is OK */
  113.     if (nbits < 0)
  114.         throw new NegativeArraySizeException(Integer.toString(nbits));
  115.  
  116.     bits = new long[(unitIndex(nbits-1) + 1)];
  117.     }
  118.  
  119.     /**
  120.      * Ensures that the BitSet can hold enough units.
  121.      * @param    unitsRequired the minimum acceptable number of units.
  122.      */
  123.     private void ensureCapacity(int unitsRequired) {
  124.     if (bits.length < unitsRequired) {
  125.         /* Allocate larger of doubled size or required size */
  126.         int request = Math.max(2 * bits.length, unitsRequired);
  127.         long newBits[] = new long[request];
  128.         System.arraycopy(bits, 0, newBits, 0, unitsInUse);
  129.         bits = newBits;
  130.     }
  131.     }
  132.  
  133.     /**
  134.      * Returns the "logical size" of this <code>BitSet</code>: the index of
  135.      * the highest set bit in the <code>BitSet</code> plus one.
  136.      *
  137.      * @return  the logical size of this <code>BitSet</code>.
  138.      * @since   JDK1.2
  139.      */
  140.     public int length() {
  141.         if (unitsInUse == 0)
  142.             return 0;
  143.  
  144.         int highestBit = (unitsInUse - 1) * 64;
  145.     long highestUnit = bits[unitsInUse - 1];
  146.     do {
  147.             highestUnit = highestUnit >>> 1;
  148.             highestBit++;
  149.         } while(highestUnit > 0);
  150.         return highestBit;
  151.     }
  152.  
  153.     /**
  154.      * Sets the bit specified by the index to <code>true</code>.
  155.      *
  156.      * @param     bitIndex   a bit index.
  157.      * @exception IndexOutOfBoundsException if the specified index is negative.
  158.      * @since     JDK1.0
  159.      */
  160.     public void set(int bitIndex) {
  161.     if (bitIndex < 0)
  162.         throw new IndexOutOfBoundsException(Integer.toString(bitIndex));
  163.  
  164.         int unitIndex = unitIndex(bitIndex);
  165.         int unitsRequired = unitIndex+1;
  166.  
  167.         if (unitsInUse < unitsRequired) {
  168.             ensureCapacity(unitsRequired);
  169.             bits[unitIndex] |= bit(bitIndex);
  170.             unitsInUse = unitsRequired;
  171.         } else {
  172.             bits[unitIndex] |= bit(bitIndex);
  173.         }            
  174.     }
  175.  
  176.     /**
  177.      * Sets the bit specified by the index to <code>false</code>.
  178.      *
  179.      * @param     bitIndex   the index of the bit to be cleared.
  180.      * @exception IndexOutOfBoundsException if the specified index is negative.
  181.      * @since     JDK1.0
  182.      */
  183.     public void clear(int bitIndex) {
  184.     if (bitIndex < 0)
  185.         throw new IndexOutOfBoundsException(Integer.toString(bitIndex));
  186.     int unitIndex = unitIndex(bitIndex);
  187.     if (unitIndex >= unitsInUse)
  188.         return;
  189.  
  190.     bits[unitIndex] &= ~bit(bitIndex);
  191.         if (unitIndex == unitsInUse-1)
  192.             recalculateUnitsInUse();
  193.     }
  194.  
  195.     /**
  196.      * Clears all of the bits in this <code>BitSet</code> whose corresponding
  197.      * bit is set in the specified <code>BitSet</code>.
  198.      *
  199.      * @param     s the <code>BitSet</code> with which to mask this
  200.      *            <code>BitSet</code>.
  201.      * @since     JDK1.2
  202.      */
  203.     public void andNot(BitSet set) {
  204.         int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
  205.  
  206.     // perform logical (a & !b) on bits in common
  207.         for (int i=0; i<unitsInCommon; i++) {
  208.         bits[i] &= ~set.bits[i];
  209.         }
  210.  
  211.         recalculateUnitsInUse();
  212.     }
  213.  
  214.     /**
  215.      * Returns the value of the bit with the specified index. The value 
  216.      * is <code>true</code> if the bit with the index <code>bitIndex</code> 
  217.      * is currently set in this <code>BitSet</code>; otherwise, the result 
  218.      * is <code>false</code>.
  219.      *
  220.      * @param     bitIndex   the bit index.
  221.      * @return    the value of the bit with the specified index.
  222.      * @exception IndexOutOfBoundsException if the specified index is negative.
  223.      */
  224.     public boolean get(int bitIndex) {
  225.     if (bitIndex < 0)
  226.         throw new IndexOutOfBoundsException(Integer.toString(bitIndex));
  227.  
  228.     boolean result = false;
  229.     int unitIndex = unitIndex(bitIndex);
  230.     if (unitIndex < unitsInUse)
  231.         result = ((bits[unitIndex] & bit(bitIndex)) != 0);
  232.  
  233.     return result;
  234.     }
  235.  
  236.     /**
  237.      * Performs a logical <b>AND</b> of this target bit set with the 
  238.      * argument bit set. This bit set is modified so that each bit in it 
  239.      * has the value <code>true</code> if and only if it both initially 
  240.      * had the value <code>true</code> and the corresponding bit in the 
  241.      * bit set argument also had the value <code>true</code>. 
  242.      *
  243.      * @param   set   a bit set. 
  244.      */
  245.     public void and(BitSet set) {
  246.     if (this == set)
  247.         return;
  248.  
  249.     // perform logical AND on bits in common
  250.     int oldUnitsInUse = unitsInUse;
  251.         int i;
  252.     unitsInUse = Math.min(unitsInUse,set.unitsInUse);
  253.     for(i=0; i<unitsInUse; i++)
  254.         bits[i] &= set.bits[i];
  255.  
  256.     // clear out units no longer used
  257.     for( ; i < oldUnitsInUse; i++)
  258.         bits[i] = 0;
  259.     }
  260.  
  261.     /**
  262.      * Performs a logical <b>OR</b> of this bit set with the bit set 
  263.      * argument. This bit set is modified so that a bit in it has the 
  264.      * value <code>true</code> if and only if it either already had the 
  265.      * value <code>true</code> or the corresponding bit in the bit set 
  266.      * argument has the value <code>true</code>.
  267.      *
  268.      * @param   set   a bit set.
  269.      */
  270.     public void or(BitSet set) {
  271.     if (this == set)
  272.         return;
  273.  
  274.     ensureCapacity(set.unitsInUse);
  275.  
  276.     // perform logical OR on bits in common
  277.     int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
  278.         int i;
  279.     for(i=0; i<unitsInCommon; i++)
  280.         bits[i] |= set.bits[i];
  281.  
  282.     // copy any remaining bits
  283.     for(; i<set.unitsInUse; i++)
  284.         bits[i] = set.bits[i];
  285.  
  286.         if (unitsInUse < set.unitsInUse)
  287.             unitsInUse = set.unitsInUse;
  288.     }
  289.  
  290.     /**
  291.      * Performs a logical <b>XOR</b> of this bit set with the bit set 
  292.      * argument. This bit set is modified so that a bit in it has the 
  293.      * value <code>true</code> if and only if one of the following 
  294.      * statements holds: 
  295.      * <ul>
  296.      * <li>The bit initially has the value <code>true</code>, and the 
  297.      *     corresponding bit in the argument has the value <code>false</code>.
  298.      * <li>The bit initially has the value <code>false</code>, and the 
  299.      *     corresponding bit in the argument has the value <code>true</code>. 
  300.      * </ul>
  301.      *
  302.      * @param   set   a bit set.
  303.      */
  304.     public void xor(BitSet set) {
  305.         int unitsInCommon;
  306.  
  307.         if (unitsInUse >= set.unitsInUse) {
  308.             unitsInCommon = set.unitsInUse;
  309.         } else {
  310.             unitsInCommon = unitsInUse;
  311.  
  312.             int newUnitsInUse = set.unitsInUse;
  313.             ensureCapacity(newUnitsInUse);
  314.             unitsInUse = newUnitsInUse;
  315.         }
  316.  
  317.     // perform logical XOR on bits in common
  318.         int i;
  319.         for (i=0; i<unitsInCommon; i++)
  320.         bits[i] ^= set.bits[i];
  321.  
  322.     // copy any remaining bits
  323.         for ( ; i<set.unitsInUse; i++)
  324.             bits[i] = set.bits[i];
  325.  
  326.         recalculateUnitsInUse();
  327.     }
  328.  
  329.     /**
  330.      * Returns a hash code value for this bit set. The has code 
  331.      * depends only on which bits have been set within this 
  332.      * <code>BitSet</code>. The algorithm used to compute it may 
  333.      * be described as follows.<p>
  334.      * Suppose the bits in the <code>BitSet</code> were to be stored 
  335.      * in an array of <code>long</code> integers called, say, 
  336.      * <code>bits</code>, in such a manner that bit <code>k</code> is 
  337.      * set in the <code>BitSet</code> (for nonnegative values of 
  338.      * <code>k</code>) if and only if the expression 
  339.      * <pre>((k>>6) < bits.length) && ((bits[k>>6] & (1L << (bit & 0x3F))) != 0)</pre>
  340.      * is true. Then the following definition of the <code>hashCode</code> 
  341.      * method would be a correct implementation of the actual algorithm:
  342.      * <pre>
  343.      * public synchronized int hashCode() {
  344.      *      long h = 1234;
  345.      *      for (int i = bits.length; --i >= 0; ) {
  346.      *           h ^= bits[i] * (i + 1);
  347.      *      }
  348.      *      return (int)((h >> 32) ^ h);
  349.      * }</pre>
  350.      * Note that the hash code values change if the set of bits is altered.
  351.      * <p>Overrides the <code>hashCode</code> method of <code>Object</code>.
  352.      *
  353.      * @return  a hash code value for this bit set.
  354.      */
  355.     public int hashCode() {
  356.     long h = 1234;
  357.     for (int i = bits.length; --i >= 0; )
  358.             h ^= bits[i] * (i + 1);
  359.  
  360.     return (int)((h >> 32) ^ h);
  361.     }
  362.     
  363.     /**
  364.      * Returns the number of bits of space actually in use by this 
  365.      * <code>BitSet</code> to represent bit values. 
  366.      * The maximum element in the set is the size - 1st element.
  367.      *
  368.      * @return  the number of bits currently in this bit set.
  369.      */
  370.     public int size() {
  371.     return bits.length << ADDRESS_BITS_PER_UNIT;
  372.     }
  373.  
  374.     /**
  375.      * Compares this object against the specified object.
  376.      * The result is <code>true</code> if and only if the argument is 
  377.      * not <code>null</code> and is a <code>Bitset</code> object that has 
  378.      * exactly the same set of bits set to <code>true</code> as this bit 
  379.      * set. That is, for every nonnegative <code>int</code> index <code>k</code>, 
  380.      * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
  381.      * must be true. The current sizes of the two bit sets are not compared. 
  382.      * <p>Overrides the <code>equals</code> method of <code>Object</code>.
  383.      *
  384.      * @param   obj   the object to compare with.
  385.      * @return  <code>true</code> if the objects are the same;
  386.      *          <code>false</code> otherwise.
  387.      * @see     java.util.BitSet#size()
  388.      */
  389.     public boolean equals(Object obj) {
  390.     if (obj == null || !(obj instanceof BitSet))
  391.         return false;
  392.     if (this == obj)
  393.         return true;
  394.  
  395.     BitSet set = (BitSet) obj;
  396.     int minUnitsInUse = Math.min(unitsInUse, set.unitsInUse);
  397.  
  398.     // Check units in use by both BitSets
  399.     for (int i = 0; i < minUnitsInUse; i++)
  400.         if (bits[i] != set.bits[i])
  401.         return false;
  402.  
  403.     // Check any units in use by only one BitSet (must be 0 in other)
  404.     if (unitsInUse > minUnitsInUse) {
  405.         for (int i = minUnitsInUse; i<unitsInUse; i++)
  406.         if (bits[i] != 0)
  407.             return false;
  408.     } else {
  409.         for (int i = minUnitsInUse; i<set.unitsInUse; i++)
  410.         if (set.bits[i] != 0)
  411.             return false;
  412.     }
  413.  
  414.     return true;
  415.     }
  416.  
  417.     /**
  418.      * Cloning this <code>BitSet</code> produces a new <code>BitSet</code> 
  419.      * that is equal to it.
  420.      * The clone of the bit set is another bit set that has exactly the 
  421.      * same bits set to <code>true</code> as this bit set and the same 
  422.      * current size. 
  423.      * <p>Overrides the <code>clone</code> method of <code>Object</code>.
  424.      *
  425.      * @return  a clone of this bit set.
  426.      * @see     java.util.BitSet#size()
  427.      */
  428.     public Object clone() {
  429.     BitSet result = null;
  430.     try {
  431.         result = (BitSet) super.clone();
  432.     } catch (CloneNotSupportedException e) {
  433.         throw new InternalError();
  434.     }
  435.     result.bits = new long[bits.length];
  436.     System.arraycopy(bits, 0, result.bits, 0, unitsInUse);
  437.     return result;
  438.     }
  439.  
  440.     /**
  441.      * This override of readObject makes sure unitsInUse is set properly
  442.      * when deserializing a bitset
  443.      *
  444.      */
  445.     private void readObject(java.io.ObjectInputStream in)
  446.         throws IOException, ClassNotFoundException {
  447.         
  448.         in.defaultReadObject();
  449.         //assume maximum length then find real length
  450.         //because recalculateUnitsInUse assumes maintenance
  451.         //or reduction in logical size
  452.         unitsInUse = bits.length;
  453.         recalculateUnitsInUse();
  454.     }
  455.  
  456.     /**
  457.      * Returns a string representation of this bit set. For every index 
  458.      * for which this <code>BitSet</code> contains a bit in the set 
  459.      * state, the decimal representation of that index is included in 
  460.      * the result. Such indeces aer listed in order from lowest to 
  461.      * highest, separated by ",$nbsp;" (a comma and a space) and 
  462.      * surrounded by braces, resulting in the usual mathematical 
  463.      * notation for a set of integers.<p>
  464.      * Overrides the <code>toString</code> method of <code>Object</code>.
  465.      * <p>Example:
  466.      * <pre>
  467.      * BitSet drPepper = new BitSet();</pre>
  468.      * Now <code>drPepper.toString()</code> returns "<code>{}</code>".<p>
  469.      * <pre>
  470.      * drPepper.set(2);</pre>
  471.      * Now <code>drPepper.toString()</code> returns "<code>{2}</code>".<p>
  472.      * <pre>
  473.      * drPepper.set(4);
  474.      * drPepper.set(10);</pre>
  475.      * Now <code>drPepper.toString()</code> returns "<code>{2, 4, 10}</code>".
  476.      *
  477.      * @return  a string representation of this bit set.
  478.      */
  479.     public String toString() {
  480.     int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT;
  481.     StringBuffer buffer = new StringBuffer(8*numBits + 2);
  482.     String separator = "";
  483.     buffer.append('{');
  484.  
  485.     for (int i = 0 ; i < numBits; i++) {
  486.         if (get(i)) {
  487.         buffer.append(separator);
  488.         separator = ", ";
  489.             buffer.append(i);
  490.         }
  491.         }
  492.  
  493.     buffer.append('}');
  494.     return buffer.toString();
  495.     }
  496. }
  497.